#include <iostream>
#include <cassert>
#include <ctime>

using namespace std;

/**
 * 二分查找,在有序数组中查找
 *找到target,返回对应索引,反之返回-1
 */
template<typename T>
int binarySearch(T arr[], int n, T target){
	// arr[l...r] 查找target
	int l = 0, r = n - 1;
	while(l <= r){
		int mid = l + (r - l) / 2;
		if(arr[mid] == target){
			return mid;
		}

		if(arr[mid] > target)
			r = mid - 1;
		else
			l = mid + 1;
	}
	return -1;
}


// recursion
template<typename T>
int __binarySearch2(T arr[], int l, int r, T target){
	if(l > r){
		return -1;
	}

	int mid = l + (r - l) / 2;
	if(arr[mid] == target){
		return mid;
	} else if (arr[mid] > target) {
		return __binarySearch2(arr,l,mid - 1,target);
	} else {
		return __binarySearch2(arr,mid + 1, r, target);
	}
}

template<typename T>
int binarySearch2(T arr[], int n, T target){
	__binarySearch2(arr, 0, n - 1, target);
}

template<typename T>
void testSearch(const string &sortName, int(*search)(T[],int, T), T arr[],int n){
	clock_t startTime = clock();
	for(int i = 0; i < 2 * n; ++i){
		int v = search(arr,n,i);
		if(i < n)
			assert( v == i);
		else
			assert(v == -1);
	}
	clock_t endTime = clock();
	cout << sortName << ": " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;
}

int main(){
	int n = 1000000;
	int* a = new int[n];
	for(int i = 0; i < n; ++i)
		a[i] = i;

	testSearch("Binary Search ",binarySearch,a,n);
	testSearch("Binary Search recursion ",binarySearch2,a,n);

	delete[] a;


}
